'''
Created on Jul 6, 2011

@author: anupam saini
'''
from com.anupam.common.utils import Utils

class HeapNode(object):
  """Class describing a heap node """

  def __init__(self, num=None):
    self.left = None
    self.right = None
    self.parent = None
    self.value = num


class HeapGeneration(object):
  """
    Class used for creating Max and Min heaps.
    This is not based on classis 2i , 2i+1 index based heap structures.
    Rather we are creating  a tree based representation of the heap and performing
    the heap operations. 
  """

  def __init__(self):
    # contains the root node of the heap, in the tree based representation used 
    self.root = None
    self.heapProperty = None

  def __swap(self, node, largerNode):
    temp = node.value
    node.value = largerNode.value
    largerNode.value = temp

  def __minHeapify(self,node):
    smallest = None
    left = node.left
    right = node.right
    
    if right:
      if left.value < right.value:
        smallest = left
      else:
        smallest = right
    else:
      smallest = left

    if smallest.value < node.value:
        ## swaps only the values, node pointer still points to largest value.
        self.__swap(node, smallest)
        # Breaks recusrion when the root node is reached.
        if node.parent:
          self.__minHeapify(node.parent)
    
  def __maxHeapify(self, node):
    """
      Maintains the Max heap property of the tree structure, i.e largest node at root
      and at each node parent is larger than the child nodes.
    """

    largest = None
    left = node.left
    right = node.right

    if right:
      if left.value > right.value:
        largest = left
      else:
        largest = right
    else:
      largest = left

    if largest.value > node.value:
        ## swaps only the values, node pointer still points to largest value.
        self.__swap(node, largest)
        # Breaks recusrion when the root node is reached.
        if node.parent:
          self.__maxHeapify(node.parent)

  
  def selectNodeDirection(self, nodeToInsert):
    """
      Determines the current node's pointer to be used, i.e node's left postion or right
      position to insert the new element.
    """
    node = self.root
    while True:
      if not node.left:
        node.left = nodeToInsert
        node.left.parent = node
        if self.heapProperty == 'MAX_HEAP':
          self.__maxHeapify(node)
        else:
          self.__minHeapify(node)
        break
      elif not node.right:
        node.right = nodeToInsert
        node.right.parent = node
        if self.heapProperty == 'MAX_HEAP':
          self.__maxHeapify(node)
        else:
          self.__minHeapify(node)
        break
      elif node.left.left and node.left.right and (not node.right.left or not node.right.right):
        ## Case when a nodes left child is fully populated , Need to look at node's
        ## right childerens childern , if any one of them is null. Use the right child of
        ## current node for next iteration of while loop.
        node = node.right
      else:
        node = node.left

  def generateHeap(self, arr, heapType='MAX_HEAP'):
    """
      Generates the MAX or Min heap.
    """
    node = HeapNode(arr[0])
    self.root = node
    self.heapProperty = heapType
    size = len(arr)
    for i in range(1, size):
      nodeToInsert = HeapNode(arr[i])
      self.selectNodeDirection(nodeToInsert)

  def traverseHeap(self):
    """
      Using the root node prints the max heap on console.
    """
    node = None
    traversedNodeStack = []
    traversedNodeStack.append(self.root)

    while len(traversedNodeStack) > 0:
      node = traversedNodeStack.pop(0)
      if node:
        print ' Node value : ' + repr(node.value)
        traversedNodeStack.append(node.left)
        traversedNodeStack.append(node.right)


if __name__ == '__main__':
  #arr = [6, 5, 3, 1, 8, 7, 2, 4]
  util = Utils()
  arr = util.generateNumbersInRange(8,0,50)
  print arr
  short = HeapGeneration()
  short.generateHeap(arr, 'MAX_HEAP')
  short.traverseHeap()
